package com.elloe.实现二叉树的Node节点.广度优先遍历;

import com.elloe.实现二叉树的Node节点.Node的Java实现.Node;

import java.util.LinkedList;

/**
 * @author ElloeStudy(Sifa Zhang)
 * @create 2022-04-09 19:51
 * To: 真常应物，真常得性，常清常静，常清静矣
 *
 * 广度优先遍历
 */
public class BFS {
    public void bfs(Node root){
        if (root == null) {
            return ;
        }

        LinkedList<Node> queue = new LinkedList<>();
        queue.offer(root); // 将根节点存入队列

        //当队列里有值时，每次取出队首的node打印，打印之后判断node是否有子节点，
        // 若有，则将子节点加入队列
        while (queue.size() > 0){
            Node node = queue.peek(); // 查看队列的头部节点，不会删除节点
            queue.poll(); // 取出（移除）对首的节点并打印
            System.out.print(node.getValue() + " ");
            if (node.getLeft() != null){
                // 如果有左节点，则将其存入队列
                queue.offer(node.getLeft());
            }
            if (node.getRight() != null){
                // 如果有右节点，则将其存入对列
                queue.offer(node.getRight());
            }
        }
    }
}
